// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-25 10:16
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.DeleteColumnsToMakeSorted;

public class copyBigBullSolutionTwo {
    // 对字符串进行划分，当遇到相同的字符串
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        int ans = 0;
        boolean[] cut = new boolean[n - 1];// 记录n-1个分割位置信息
        search:
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (!cut[j] && strs[j].charAt(i) > strs[j + 1].charAt(i)) {
                    // 不存在分割符号，即前面没有字符元素相同
                    ans++;
                    continue search;
                }
            }
            // 更新分割符信息
            for (int j = 0; j < n - 1; j++) {
                if (strs[j].charAt(i) < strs[j + 1].charAt(i)) {
                    cut[j] = true;
                }
            }
        }
        return ans;
    }
}
